package 剑指offer;

import util.LogUtils;

import com.sun.swing.internal.plaf.basic.resources.basic;


/**
 * 回溯法：机器人的运动范围

题目大意
		　
	 地上有一个m行n列的方格。一个机器人从坐标（0,0）的格子开始移动，它每次可以向左，向右，向上，向下移动一格，但不能进入行坐标和列坐标的位数之和大于k的格子。
	 例如：当k为18时，机器人能够进入方格（35,37），因为3+5+3+7 = 18；但它不能进入方格（35,38），因为3 + 5+3+8 = 19.请问该机器人最多能到达多少个格子？
解题思路

* 输入描述：请输入限制条件k: 
*           5 
*           请输入方格的行数m： 
*           10 
*           请输入方格的列数n: 
*           10 
* 程序输出： 矩阵能到达的方格数是： 
*           21 
* 问题分析：  
* 算法描述： 这个方格也可以看出一个m*n的矩阵。同样在这个矩阵中，除边界上的格子之外其他格子都有四个相邻的格子。  
*       　　机器人从坐标(0,0)开始移动。当它准备进入坐标为(i,j)的格子时，通过检查坐标的数位和来判断机器人是否能够进入。 
*           如果机器人能够进入坐标为(i,j)的格子，我们接着再判断它能否进入四个相邻的格子(i,j-1)、(i-1,j),(i,j+1)和(i+1,j)。 
*           
	http://blog.csdn.net/gg543012991/article/details/52900234
	@Date 2017-11-11 15：23
 *
 */
public class _013_Solution {
	
	private static final String TAG = "回溯法：机器人的运动范围";

	private boolean[]   mIsVisited;
	private int mRowCount, mColCount;
	private int mCount = 0;
	
	public int solution(int threshold, int rowCount, int colCount) {
		initMatrix(rowCount, colCount);
		movingCountCore(threshold, 0, 0);								//从(0,0)开始移动
		for (int i = 0; i < mIsVisited.length; i ++) {
			if (mIsVisited[i])	mCount ++;
		}
		LogUtils.println(TAG, "格子数"+mCount);
		return mCount;
	}
	
	private void initMatrix(int rowCount, int colCount) {
		mRowCount = rowCount;
		mColCount = colCount;
		mIsVisited = new boolean[rowCount * colCount];
		for (int i = 0; i < rowCount*colCount; i ++)	mIsVisited[i] = false;	//默认全部置为false
	}
	
	private void movingCountCore(int threshold, int row, int col) {

		if (isSafety(threshold, row, col)) {
			int index = row*mColCount+col;
			LogUtils.println("index", index);
			mIsVisited[row*mColCount+col] = true;
//			count += movingCountCore(threshold, row+1, col)
//				   + movingCountCore(threshold, row-1, col)
//				   + movingCountCore(threshold, row, col+1)
//				   + movingCountCore(threshold, row, col-1)
//				   + 1;
			movingCountCore(threshold, row+1, col);
			movingCountCore(threshold, row-1, col);
			movingCountCore(threshold, row, col+1);
			movingCountCore(threshold, row, col-1);
		}
		return;
	}
	
	private boolean isSafety(int threshold, int row, int col) {
		if (row>=0 && col>=0 && row<mRowCount && col<mColCount
				&& calDigitalSum(row)+calDigitalSum(col) <= threshold
				&& !mIsVisited[row*mColCount+col])
			return true;
		return false;
	}

	private int calDigitalSum(int num) {
		int sum = 0;
		while (num > 0) {
			int val = num%10;
			sum += val;
			num = num/10;
		}
		return sum;
	}
	
	public static void main(String[] args) {
		System.out.println(">>>"+new _013_Solution().solution(5, 10, 10));
//		System.out.println(">>>"+new _013_Solution().calDigitalSum(-1));
	}
}
